/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-22 10:51:56
 * @LastEditors: lily
 * @LastEditTime: 2021-04-22 11:17:18
 */
/*
 * @lc app=leetcode.cn id=55 lang=javascript
 *
 * [55] 跳跃游戏
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {boolean}
 */
//  思路：动态规划
//  https://leetcode-cn.com/problems/jump-game/solution/tiao-yue-you-xi-dong-tai-gui-hua-jian-da-ndz1/
//  复杂度：O(n) O(1)
var canJump = function (nums) {
    let maxdis = 0
    for (let i = 0; i < nums.length; i++) {
        // 当前能到达的最大距离小于当前位置
        if (maxdis < i) {
            return false
        }
        // 比较之前存储的最远距离 与当前能跳的最远距离
        maxdis = Math.max(maxdis, i + nums[i])
    }
    return true
};
// @lc code=end

console.log(canJump([3, 2, 1, 0, 4]));